package top.minuy.subject.leetcode._1392;

/**
 * 使用字符串哈希的方式解决问题
 * <p>
 * 1392. 最长快乐前缀
 * 「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
 * <p>
 * 给你一个字符串 s，请你返回它的 最长快乐前缀。
 * <p>
 * 如果不存在满足题意的前缀，则返回一个空字符串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "level"
 * 输出："l"
 * 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
 * 示例 2：
 * <p>
 * 输入：s = "ababab"
 * 输出："abab"
 * 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
 * 示例 3：
 * <p>
 * 输入：s = "leetcodeleet"
 * 输出："leet"
 * 示例 4：
 * <p>
 * 输入：s = "a"
 * 输出：""
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 10^5
 * s 只含有小写英文字母
 * 通过次数8,268提交次数20,254
 *
 * @author Minuy
 * @time 21:22
 * @date 2021/11/12
 */
public class Solution {
    private final static long MOD = (long) (1e9 + 7);
    // 预处理
    static long[] pow26;

    /**
     * 使用KMP算法中的next函数完成
     *
     * @param s 待处理字符串
     * @return String 最长快乐前缀
     * @author Minuy
     * @date 2021/11/14 18:59
     */
    public String longestPrefix(String s) {
        int[] next = new int[s.length()];

//
//        next[0] = -1;
//        for (int i = 1,j = -1; i < s.length(); i++) {
//            if (s.charAt(j + 1) == s.charAt(i)) {
//                j++; // 如果遇到相同的，往下走
//            } else  {
//                // 如果不同，且j！=-1的，一直回溯
//                while (j != -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
//            }
//            next[i] = j; // 记录j的值
//        }


//        {
//            int i = 0;
//            // int max = -1;
//            int j = -1;
//            next[0] = -1;
//            while (i < s.length() - 1) {
//                if(s.charAt(j+1) == s.charAt(i)){
//                    j++;
//                    i++;
//                }else {
//                    j =
//                }
//            }
//        }

        // 下面这个不是正经的next函数，测试用例"www.23" "ww."不通过，只适用于本题
        next[0] = -1;
        for (int i = 1, j = -1; i < s.length(); i++) {
            while (j != -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
            if (s.charAt(i) == s.charAt(j + 1)) j += 1;
            next[i] = j;
        }
//
//        for (int i = 0; i < next.length; i++) {
//            System.out.print(next[i]);
//            if (i != next.length - 1) {
//                System.out.print(',');
//            }
//        }
//        System.out.println();

        int e = next[s.length() - 1] + 1;
        return s.substring(0, e);
    }

    // 这种处理方式不适合测试的用例比较少的情况（75）
//    static {
//        pow26 = new long[1000010];
//        pow26[0] = 1;
//        for (int i = 1; i < pow26.length; i++) {
//            pow26[i] = (pow26[i - 1] * 26) % MOD;
//        }
//    }

    /**
     * 版本2 从后面开始处理
     * 需要预处理
     *
     * @param s 字符串
     * @return String
     * @author Minuy
     * @date 2021/11/13 0:51
     */
    public String longestPrefix2(String s) {
        // hash([1,s.length-1])
        long[] preHash = new long[s.length()];
        // hash([s.length-1,1])
        long[] postHash = new long[s.length()];

        preHash[0] = s.charAt(0) - 'a';
        postHash[s.length() - 1] = s.charAt(s.length() - 1) - 'a';

        long pow26 = 26;

        for (int i = 1; i < s.length(); i++) {
            preHash[i] = ((preHash[i - 1] * 26) + (s.charAt(i) - 'a')) % MOD;
            // 不细心，下面的代码改了一个多小时
            // preHash[i] = ((postHash[i - 1] * 26) + (s.charAt(i) - 'a')) % MOD;
            postHash[s.length() - 1 - i] = (((s.charAt(s.length() - i - 1) - 'a') * pow26) + postHash[s.length() - i]) % MOD;
            pow26 = (pow26 * 26) % MOD;
        }
        // [1,s.length-1]
        for (int len = s.length() - 1; len > 0; len--) {
            // [0, len-1] , [s.length-len,s.length-1]
            if (preHash[len - 1] == postHash[s.length() - len] && eq(s, s.length() - len, len)) {
                return s.substring(0, len);
            }
        }
        return "";
    }

    /**
     * 版本1 从前面开始处理
     *
     * @param s 字符串
     * @return String
     * @author Minuy
     * @date 2021/11/13 0:51
     */
    public String longestPrefix1(String s) {
        pow26 = new long[s.length()];
        pow26[0] = 1;
        for (int i = 1; i < pow26.length; i++) {
            pow26[i] = (pow26[i - 1] * 26) % MOD;
        }
        int preIndex = 0; // 快乐前缀[0,preIndex);
        long preHash = 0, postHash = 0;
        // StringBuilder stringBuilder = new StringBuilder();
        // [0,i]  [j,s.length-1]
        for (int i = 0, j = s.length() - 1; j > 0; i++, j--) {
            preHash = ((preHash * 26) + (s.charAt(i) - 'a')) % MOD;
            postHash = (((s.charAt(j) - 'a') * pow26[s.length() - j - 1]) + postHash) % MOD;

            if (preHash == postHash) {
                if (eq(s, j, i + 1)) {
                    preIndex = i + 1;
                    // stringBuilder.append(c);
                }
            }
        }
        //
//        char[] chars = new char[preIndex];
//        for (int i = 0; i < chars.length; i++) {
//            chars[i] = s.charAt(i);
//        }
//        return new String(chars);
        return s.substring(0, preIndex);
    }

    // 对比 [i1, i1+l) 与 [i2,i2+len) 的元素是否相等
    private boolean eq(String s, int i2, int len) {
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != s.charAt(i2)) {
                return false;
            }
            i2++;
        }
        return true;
    }

    public static void main(String[] args) {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < 1e5; i++) {
            s.append('a');
        }
        long startTime = System.nanoTime();
        System.out.println(new Solution().longestPrefix("a"));
        System.out.println(new Solution().longestPrefix("level"));
        System.out.println(new Solution().longestPrefix("leetcode"));
        System.out.println(new Solution().longestPrefix("ababab"));
        System.out.println(new Solution().longestPrefix("cbcbcba"));
        System.out.println(new Solution().longestPrefix(s.toString()));
        long endTime = System.nanoTime();

        System.out.println(":" + ((endTime - startTime) / 1e9) + " s");
//        System.out.print("{");
//        for (int i = 0; i < pow26.length; i++) {
//            System.out.print(pow26[i]);
//            if (i != pow26.length - 1) {
//                System.out.print(",");
//            }
//        }
//        System.out.print("}");
    }
}

/*
执行结果：
通过
显示详情
添加备注

执行用时：
28 ms
, 在所有 Java 提交中击败了
8.20%
的用户
内存消耗：
40.4 MB
, 在所有 Java 提交中击败了
9.84%
的用户
通过测试用例：
75 / 75
 */
